import java.util.Arrays;

/**
 * @author WangTianyi
 * @create 2021-12-08 20:32
 */
public class Self_CountSort {
    public static void main(String[] args) {

        int[] array1 = generateIntArray(100,0,10);
        int[] sortedArray1 = countSort1(array1, 10);
        System.out.println(Arrays.toString(sortedArray1));

        int[] array2 = generateIntArray(100,30,40);
        int[] sortedArray2 = countSort2(array2, 30, 40);
        System.out.println(Arrays.toString(sortedArray2));

        int[] array3 = generateIntArray(100,30,40);
        int[] sortedArray3 = countSort2(array3, 30, 40);
        System.out.println(Arrays.toString(sortedArray3));
    }

    //计数排序
    public static int[] countSort1(int[] array, int max){//默认从0开始，建立从0到max的数组
        int[] result = new int[array.length];
        int[] count = new int[max+1];
        for (int i = 0; i < array.length; i++) {
            count[array[i]]++;
        }
        for (int i = 0, j=0; i < count.length; i++) {
            while (count[i]>0){
                result[j++] = i;
                count[i]--;
            }
        }
        return result;
    }

    //countSort2为countSort1的改进版，改进了原数组中数值取值下限大于0的情况
    public static int[] countSort2(int[] array, int min, int max){//建立从min到max的数组，0<=min<=max
        int[] result = new int[array.length];
        int[] count = new int[max-min+1];
        for (int i = 0; i < array.length; i++) {
            count[array[i]-min]++;
        }
        for (int i = 0, j=0; i < count.length; i++) {
            while (count[i]>0){
                result[j++] = i+min;
                count[i]--;
            }
        }
        return result;
    }


    //countSort3是countSort2的改进版，解决了稳定性的问题，使得该算法从不稳定变得稳定。
    public static int[] countSort3(int[] array, int min, int max){
        int[] result = new int[array.length];
        int[] count = new int[max-min+1];//count是累加数组，不再是计数数组
        for (int i = 0; i < array.length; i++) {
            count[array[i]-min]++;
        }
        for (int i = 1; i < count.length; i++) {
            count[i] = count[i] + count[i-1];
        }
        for (int i = array.length-1; i >= 0; i--) {
            result[--count[i-min]] = array[i];
        }
        return result;
    }

    public static int[] generateIntArray(int length, int min, int max){
        int[] array = new int[length];
        for (int i = 0; i < length; i++) {
            array[i] = (int)(Math.random()*(max-min+1)+min);//确保数组中每个数都在0到10之间
        }
        return array;
    }
}
